package string;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/1 18:50
 * 实现 strStr() 函数。  同java中的indexOf
 *
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class StrStr {

    public static int strStr(String haystack, String needle) {
        if (needle.equals("")) {
            return 0;
        }
        //数组从1开始
        int i = 1, j = 1;
        int s = haystack.length(), t = needle.length();
        //开辟多一个空间
        int[] nextval = new int[t+1];
        //初始化nextval数组
        getNextVal(needle, nextval);
        while (i <= s && j <= t) {
            //两字符相等继续比较
            if (j == 0 || haystack.charAt(i-1) == needle.charAt(j-1)) {
                i++;
                j++;
            }else{
                //两字符不相等，主串与模式串第j个位置进行比较
                j = nextval[j];
            }
        }
        if (j > t) {
            //返回第一次匹配时的索引
            return i - t - 1;
        } else {
            return -1;
        }
    }

    public static void getNextVal(String t, int[] nextval) {
        int i = 1, j = 0;
        nextval[1] = 0;
        while (i < t.length()) {
            if (j == 0 || t.charAt(j-1) == t.charAt(i-1)) {
                i++;
                j++;
                if (t.charAt(j-1) != t.charAt(i-1)) {
                    // 相当于 nextval[i] = nextval[i-1] + 1
                    nextval[i] = j;
                }else{
                    //优化
                    nextval[i] = nextval[j];
                }
            }else{
                //返回
                j = nextval[j];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(strStr("mississippi" , "a"));
    }
}
